package minamal_DFA;

import Others.Edge;
import Others.Spot;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class SimplifyDFA {
    private DFA minamalDFA;
    private char E[];

    public SimplifyDFA(DFA minamalDFA) {
        this.minamalDFA = minamalDFA;
        this.E = minamalDFA.getE();
        Group group[];
        group = iniDFA(minamalDFA);
        group = minamalGroup(group);
        minamalDFA = newDFA(group);
        Display(minamalDFA);
    }

    //初始化划分
    Group[] iniDFA(DFA Dfa) {

        //Group初始化
        Group group[] = new Group[2];
        group[0] = new Group();
        group[1] = new Group();

        //进行分组划分
        char F_state[] = new char[Dfa.getF().length];
        for (int i = 0; i < Dfa.getF().length; i++) {
            F_state[i] = Dfa.getF()[i];
        }
        group[1].setState(F_state);

        char H_state[] = new char[Dfa.getState().length - Dfa.getF().length];
        int k = 0;
        label1:
        for (int i = 0; i < Dfa.getState().length; i++) {
            label2:
            for (int j = 0; j < F_state.length; j++) {
                if (Dfa.getState()[i] == F_state[j]) {
                    continue label1;
                }
            }
            H_state[k] = Dfa.getState()[i];
            ++k;
            continue label1;
        }

        group[1].setState(F_state);
        group[0].setState(H_state);

        //设置组号
        group[0].setGroupNum(0);
        group[1].setGroupNum(1);

        //设置终态标记符
        group[0].setIsF('F');
        group[1].setIsF('Y');

        //设置组结点
        Spot group_Hspot[] = new Spot[H_state.length];
        for (int i = 0; i < H_state.length; i++) {
            group_Hspot[i] = new Spot();
            group_Hspot[i].setGroupNum(0);
            group_Hspot[i].setStateNum(H_state[i]);
        }
        Spot group_Fspot[] = new Spot[F_state.length];
        for (int i = 0; i < F_state.length; i++) {
            group_Fspot[i] = new Spot();
            group_Fspot[i].setGroupNum(1);
            group_Fspot[i].setStateNum(F_state[i]);
        }

        group[0].setSpot(group_Hspot);
        group[1].setSpot(group_Fspot);

        //设置move状态转移集
        int count = 0;
        for (int i = 0; i < Dfa.getMove().length; i++) {
            for (int j = 0; j < group[1].getState().length; j++) {
                if (Dfa.getMove()[i].getFirstSpot() == group[1].getState()[j]) {
                    ++count;
                } else {
                    continue;
                }
            }
        }
        Edge F_move[] = new Edge[count];
        int z = 0;
        for (int i = 0; i < Dfa.getMove().length; i++) {
            for (int j = 0; j < group[1].getState().length; j++) {
                if (Dfa.getMove()[i].getFirstSpot() == group[1].getState()[j]) {
                    F_move[z] = Dfa.getMove()[i];
                    F_move[z].setOldGroupNum(-1);
                    F_move[z].setMewGroupNum(1);
                    ++z;
                } else {
                    continue;
                }
            }
        }

        Edge H_move[] = new Edge[Dfa.getMove().length - count];
        int Hm = 0;
        label1:
        for (int i = 0; i < Dfa.getMove().length; i++) {
            label2:
            for (int j = 0; j < group[1].getState().length; j++) {
                if (Dfa.getMove()[i].getFirstSpot() == group[1].getState()[j]) {
                    continue label1;
                }
            }
            H_move[Hm] = Dfa.getMove()[i];
            H_move[Hm].setOldGroupNum(-1);
            H_move[Hm].setMewGroupNum(0);
            ++Hm;
            continue label1;
        }

        group[0].setMove(H_move);
        group[1].setMove(F_move);

        return group;
    }

    //递归划分
    Group[] minamalGroup(Group oldGroup[]) {
        boolean flag = false;
        int groupNum = oldGroup.length;
        Queue<Integer> index = new LinkedBlockingQueue<>();   //记录新划分的值
        Queue<Edge> EdgeQueue = new LinkedBlockingQueue<>();   //存放move新划分

        //获取第二个group中所有state
        int group_length = oldGroup.length - 1;
        char oldState[] = new char[oldGroup[1].getState().length];
        for (int i = 0; i < oldGroup[1].getState().length; i++) {
            oldState[i] = oldGroup[1].getState()[i];
        }

        char identity = ' ';
        for (int i = 0; i < oldGroup[0].getMove().length; i++) {
            for (int j = 0; j < oldState.length; j++) {
                if (oldGroup[0].getMove()[i].getRearSpot() == oldState[j]) {
                    ++groupNum;
                    EdgeQueue.add(oldGroup[0].getMove()[i]);
                    identity = oldGroup[0].getMove()[i].getFirstSpot();
                    index.add(i);
//                    flag=true;
                } else {
                    continue;
                }
            }
        }

        char inputChar[] = new char[E.length];
        for (int i = 0; i < E.length; i++) {
            inputChar[i] = E[i];
        }
        Edge flagEdge[][] = new Edge[E.length][(oldGroup[0].getMove().length) / E.length];
        for (int i = 0; i < E.length; i++) {
            int jj = 0;
            Edge ee[] = new Edge[(oldGroup[0].getMove().length) / E.length];
            for (int kk = 0; kk < oldGroup[0].getMove().length; kk++) {
                if (oldGroup[0].getMove()[kk].getCh() == E[i]) {
                    ee[jj++] = oldGroup[0].getMove()[kk];
                }
            }

            for (int kk = 0; kk < (oldGroup[0].getMove().length) / E.length; kk++) {
                flagEdge[i][kk] = ee[kk];
            }
        }

        lable2:
        for (int i = 0; i < (oldGroup[0].getMove().length) / E.length; i++) {
            lable1:
            for (int mm = 0; mm < (oldGroup[0].getMove().length) / E.length - 1; mm++) {
                if (flagEdge[i][mm].getRearSpot() != flagEdge[i][mm + 1].getRearSpot()) {
                    flag = true;
                    break lable2;
                }
            }
        }


        if (flag == false) {
            return oldGroup;
        }

        for (int i = 0; i < oldGroup[0].getMove().length; i++) {
            for (int j = 0; j < oldState.length; j++) {
                if (oldGroup[0].getMove()[i].getRearSpot() != oldState[j] && identity == oldGroup[0].getMove()[i].getFirstSpot()) {
                    EdgeQueue.add(oldGroup[0].getMove()[i]);
                    index.add(i);
                    flag = true;
                } else {
                    continue;
                }
            }
        }

        //初始化新Group
        Group newGroup[] = new Group[groupNum];
        for (int i = 0; i < groupNum; i++) {
            newGroup[i] = new Group();
        }
        newGroup[groupNum - 1] = oldGroup[oldGroup.length - 1];


        //设置move转移函数
        Edge firstMove[] = new Edge[oldGroup[0].getMove().length - index.size()];
        for (int i = 0; i < oldGroup[0].getMove().length - index.size(); i++) {
            firstMove[i] = new Edge();
        }
        int j = 0;
        for (int i = 0; i < oldGroup[0].getMove().length - index.size(); i++) {
            if (index.contains(j)) {
                --i;
                ++j;
                continue;
            } else {
                firstMove[i] = oldGroup[0].getMove()[j];
            }
            ++j;
        }
        newGroup[0].setMove(firstMove);

        Edge newMove[] = new Edge[index.size()];
        for (int i = 0; i < index.size(); i++) {
            newMove[i] = new Edge();
            newMove[i] = EdgeQueue.poll();
            newMove[i].setMewGroupNum(1);
        }
        newGroup[1].setMove(newMove);

        for (int i = newGroup.length - 2; i >= 2; i--) {
            newGroup[i].setMove(oldGroup[i - 1].getMove());
        }

        //设置State
        char Second[] = new char[newGroup.length - 2];
        for (int i = 1; i < newGroup.length - 1; i++) {
            Second[i - 1] = newGroup[i].getMove()[0].getFirstSpot();
            char SecondSpot[] = new char[1];
            SecondSpot[0] = newGroup[i].getMove()[0].getFirstSpot();
            newGroup[i].setState(SecondSpot);
        }
        char FirstSpot[] = new char[oldGroup[0].getState().length - 1];
        int qq = 0;
        for (int i = 0; i < oldGroup[0].getState().length - 1; i++) {
            if (Second[0] == oldGroup[0].getState()[qq]) {
                --i;
                ++qq;
                continue;
            } else {
                FirstSpot[i] = oldGroup[0].getState()[qq];
            }
            ++qq;
        }
        newGroup[0].setState(FirstSpot);

        //设置数组号
        for (int i = 0; i < newGroup.length; i++) {
            newGroup[i].setGroupNum(i);
        }

        //设置终态数组
        for (int i = 0; i < newGroup.length - 1; i++) {
            newGroup[i].setIsF('F');
        }
        newGroup[newGroup.length - 1].setIsF('T');

        //设置spot
        for (int i = 0; i < newGroup.length; i++) {
            Spot newSpot[] = new Spot[newGroup[i].getState().length];
            for (int y = 0; y < newGroup[i].getState().length; y++) {
                newSpot[y] = new Spot();
            }
            for (int l = 0; l < newGroup[i].getState().length; l++) {
                newSpot[l].setGroupNum(i);
                newSpot[l].setStateNum(newGroup[i].getState()[l]);
            }
            newGroup[i].setSpot(newSpot);
        }

        return minamalGroup(newGroup);
    }

    //重新命名新的状态集
    DFA newDFA(Group group[]) {
        DFA newDFA = new DFA();

        //设置合法字符集
        newDFA.setE(E);

        //更新并设置状态集
        char newState[] = new char[group.length];
        for (int i = 0; i < group.length; i++) {
            newState[i] = (char) (i % 26 + (int) 'A');
        }
        newDFA.setState(newState);

        //设置起点
        newDFA.setS0(newState[0]);

        //设置终点集
        int F_identity = 0;
        Queue<Integer> index = new LinkedBlockingQueue<>();
        for (int i = 0; i < group.length; i++) {
            if (group[i].getIsF() == 'T') {
                ++F_identity;
                index.add(i);
            }
        }

        char F[] = new char[F_identity];
        for (int i = 0; i < F_identity; i++) {
            F[i] = (char) ((index.poll().intValue()) % 26 + (int) 'A');
        }
        newDFA.setF(F);


        //设置move函数
        int move_identity = 0;
        for (int i = 0; i < group.length; i++) {
            move_identity = move_identity + (group[i].getMove().length / group[i].getState().length);
        }
        Edge new_Move[] = new Edge[move_identity];
        for (int i = 0; i < move_identity; i++) {
            new_Move[i] = new Edge();
        }

        Queue<Edge> new_Move_Edge = new LinkedBlockingQueue<>();
        char modify_char[] = new char[100];
        int modify_char_num = 0;
        for (int i = 0; i < group.length; i++) {
            for (int j = 0; j < group[i].getMove().length; j++) {
                if (group[i].getState().length != 1) {
                    modify_char_num = group[i].getState().length - 1;
                }
                for (int k = 0; k < group[i].getState().length - 1; k++) {
                    modify_char[modify_char_num - 1] = group[i].getState()[k + 1];
                }
                boolean flag = false;
                boolean flag2 = false;
                label1:
                for (int w = modify_char_num - 1; w >= 0; w--) {
                    label2:
                    for (int m = 0; m < group[i].getState().length; m++) {
                        if (group[i].getMove()[j].getRearSpot() == modify_char[w]) {
                            flag = true;
                            break label1;
                        }
                    }
                }

                label3:
                for (int w = modify_char_num - 1; w >= 0; w--) {
                    label4:
                    for (int m = 0; m < group[i].getState().length; m++) {
                        for (int ww = 0; ww < modify_char.length; ww++) {
                            if (group[i].getMove()[j].getFirstSpot() == modify_char[ww] || group[i].getMove()[j].getFirstSpot() == (char) (i % 26 + (int) 'A')) {
                                flag2 = true;
                                break label3;
                            }
                        }
                    }
                }

                group[i].getMove()[j].setFirstSpot((char) (i % 26 + (int) 'A'));
                group[i].getMove()[j].setCh(group[i].getMove()[j].getCh());
                if (flag == true && flag2 == false) {
                    int ii = 0;
                    for (int cc = 0; cc < i - 1; cc++) {
                        if (group[i].getState().length == 1) {
                            ++ii;
                        } else {
                            int w = group[i].getState().length;
                            ii = ii + (w - 1);
                        }
                    }
                    group[i].getMove()[j].setRearSpot((char) ((ii - modify_char_num - 1) % 26 + (int) 'A'));
                } else if (flag == true && flag2 == true) {
                    group[i].getMove()[j].setRearSpot((char) ((i % 26 + (int) 'A')));
                } else if (flag == false && modify_char[modify_char_num - 1] <= group[i].getMove()[j].getRearSpot()) {
                    int c1 = (int) group[i].getMove()[j].getRearSpot();
                    int c2 = ((int) group[i].getMove()[j].getRearSpot() - modify_char_num);
                    char m = (char) (((int) group[i].getMove()[j].getRearSpot() - modify_char_num));
                    group[i].getMove()[j].setRearSpot((char) (((int) group[i].getMove()[j].getRearSpot() - modify_char_num)));
                } else {
                    group[i].getMove()[j].setRearSpot(group[i].getMove()[j].getRearSpot());
                }

            }
        }

        Queue<Edge> new_Edge = new LinkedBlockingQueue<>();
        boolean kw=true;
        label5:
        for (int i = 0; i < group.length; i++) {
            label6:
            for (int j = 0; j < group[i].getMove().length; j++) {
                kw=true;
                label7:
                for (int kk = j+1; kk < group[i].getMove().length; kk++) {
                    if (group[i].getMove()[j].getFirstSpot() == group[i].getMove()[kk].getFirstSpot()
                            && group[i].getMove()[j].getRearSpot() == group[i].getMove()[kk].getRearSpot()
                            && group[i].getMove()[j].getCh() == group[i].getMove()[kk].getCh()) {
                        kw=false;
                        break label7;
                    }
                }
                if(kw==true){
                    new_Edge.add(group[i].getMove()[j]);
                }
            }
        }

        int v=new_Edge.size();
        Edge c[]=new Edge[new_Edge.size()];
        for(int lll=new_Edge.size()-1;lll>=0;lll--){
            c[lll]=new_Edge.poll();
        }
        newDFA.setMove(c);

        return newDFA;
    }


    /**
     * 显示最小DFA
     */
    void Display(DFA Dfa){
        DFA A=Dfa;
        int c=0;
        System.out.print("状态集： ");
        for (int i=0;i<Dfa.getState().length;i++){
            System.out.print(Dfa.getState()[i]+" ");
        }
        System.out.println();

        System.out.print("合法字符集： ");
        for (int i=0;i<Dfa.getE().length;i++){
            System.out.print(Dfa.getE()[i]+" ");
        }
        System.out.println();

        System.out.println("起点： "+Dfa.getS0());

        System.out.print("终点： ");
        for (int i=0;i<Dfa.getF().length;i++){
            System.out.print(Dfa.getF()[i]);
        }
        System.out.println();

        System.out.println("move函数： （ 共 "+Dfa.getMove().length+" 个 ）");
        for(int i=0;i<Dfa.getMove().length;i++){
            System.out.println("move( "+Dfa.getMove()[i].getFirstSpot()+" , "+Dfa.getMove()[i].getCh()+" ) = "+Dfa.getMove()[i].getRearSpot());
        }
        System.out.println();
    }
}
